//
// Description: 56. 合并区间
// Created by Loading on 2022/3/20.
//

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> merge(vector<vector<int>> &intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> res;

    // 维护两个端点
    int start = -1, end = -1;
    for (const auto &v : intervals) {
        if (v[0] > end) {
            // 新区间完成
            if (start != -1) {
                res.push_back({start, end});
            }
            // 更新左右端点
            start = v[0], end = v[1];
        } else {
            // 更新右端点
            end = max(end, v[1]);
        }
    }
    // 防止遗忘最后一个区间
    if (end != -1) {
        res.push_back({start, end});
    }

    return res;
}

int main() {
    vector<vector<int>> intervals{{1, 4},
                                  {0, 0}};
    auto res = merge(intervals);
    for (auto &v : res) {
        cout << v[0] << ' ' << v[1] << endl;
    }

    return 0;
}